Search Results

Documents authored by Huisman, Dennis

Document
DOI: 10.4230/OASIcs.ATMOS.2023.8
Fewer Trains for Better Timetables: The Price of Fixed Line Frequencies in the Passenger-Oriented Timetabling Problem

Authors: Pedro José Correia Duarte, Marie Schmidt, Dennis Huisman, and Lucas P. Veelenturf

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
This paper introduces the Passenger-Oriented Timetabling problem with flexible frequencies (POT-flex) in the context of railway planning problems. POT-flex aims at creating feasible railway timetables minimising total perceived passenger travel time. The contribution of the POT-flex lies in its relaxation of the generally adopted assumption that line frequencies should be a fixed part of the input. Instead, we consider flexible line frequencies, encompassing a minimum and maximum frequency per line, allowing the timetabling model to decide on optimal line frequencies to obtain better solutions using fewer train services per line. We develop a mixed-integer programming formulation for POT-flex based on the Passenger-Oriented Timetabling (POT) formulation of [Polinder et al., 2021] and compare the performance of the new formulation against the POT formulation on three instances. We find that POT-flex allows to find feasible timetables in instances containing bottlenecks, and show improvements of up to 2% on the largest instance tested. These improvements highlight the cost that fixed line frequencies can have on timetabling.
Cite as

Pedro José Correia Duarte, Marie Schmidt, Dennis Huisman, and Lucas P. Veelenturf. Fewer Trains for Better Timetables: The Price of Fixed Line Frequencies in the Passenger-Oriented Timetabling Problem. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{correiaduarte_et_al:OASIcs.ATMOS.2023.8,
  author =	{Correia Duarte, Pedro Jos\'{e} and Schmidt, Marie and Huisman, Dennis and Veelenturf, Lucas P.},
  title =	{{Fewer Trains for Better Timetables: The Price of Fixed Line Frequencies in the Passenger-Oriented Timetabling Problem}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{8:1--8:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.8},
  URN =		{urn:nbn:de:0030-drops-187695},
  doi =		{10.4230/OASIcs.ATMOS.2023.8},
  annote =	{Keywords: PESP, Passenger Oriented Timetabling, Perceived Travel Time}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2020
OASIcs, Volume 85, ATMOS 2020, Complete Volume

Authors: Dennis Huisman and Christos D. Zaroliagis

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
OASIcs, Volume 85, ATMOS 2020, Complete Volume
Cite as

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 1-272, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{huisman_et_al:OASIcs.ATMOS.2020,
  title =	{{OASIcs, Volume 85, ATMOS 2020, Complete Volume}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{1--272},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020},
  URN =		{urn:nbn:de:0030-drops-131356},
  doi =		{10.4230/OASIcs.ATMOS.2020},
  annote =	{Keywords: OASIcs, Volume 85, ATMOS 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Dennis Huisman and Christos D. Zaroliagis

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huisman_et_al:OASIcs.ATMOS.2020.0,
  author =	{Huisman, Dennis and Zaroliagis, Christos D.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.0},
  URN =		{urn:nbn:de:0030-drops-131363},
  doi =		{10.4230/OASIcs.ATMOS.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.7
Analyzing a Family of Formulations for Cyclic Crew Rostering

Authors: Thomas Breugem, Twan Dollevoet, and Dennis Huisman

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
In this paper, we analyze a family of formulations for the Cyclic Crew Rostering Problem (CCRP), in which a cyclic roster has to be constructed for a group of employees. Each formulation in the family is based on a partition of the roster. Intuitively, finer partitions give rise to a formulation with fewer variables, but possibly more constraints. Coarser partitions lead to more variables, but might allow to incorporate many of the constraints implicitly. We derive analytical results regarding the relative strength of the different formulations, which can serve as a guideline for formulating a given problem instance. Furthermore, we propose a column generation approach, and use it to compare the strength of the formulations empirically. Both the theoretical and computational results demonstrate the importance of choosing a suitable formulation. In particular, for practical instances of Netherlands Railways, stronger lower bounds are obtained, and more than 90% of the roster constraints can be modeled implicitly.
Cite as

Thomas Breugem, Twan Dollevoet, and Dennis Huisman. Analyzing a Family of Formulations for Cyclic Crew Rostering. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{breugem_et_al:OASIcs.ATMOS.2020.7,
  author =	{Breugem, Thomas and Dollevoet, Twan and Huisman, Dennis},
  title =	{{Analyzing a Family of Formulations for Cyclic Crew Rostering}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{7:1--7:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.7},
  URN =		{urn:nbn:de:0030-drops-131438},
  doi =		{10.4230/OASIcs.ATMOS.2020.7},
  annote =	{Keywords: Crew Planning, Roster Sequence, Column Generation, Railway Optimization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2009.2143
Delay Management with Re-Routing of Passengers

Authors: Twan Dollevoet, Dennis Huisman, Marie Schmidt, and Anita Schoebel

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)

Abstract
Trains often arrive delayed at stations where passengers have to change to other trains. The question of delay management is whether these trains should wait for the original train or depart on time. In traditional delay management models passengers always take their originally planned route. This means, they are in case of a missed connection always delayed with the cycle time of the timetable. In this paper, we propose a model where re-routing of passengers is incorporated. \\ To describe the problem we represent it as an event-activity network similar to the one used in traditional delay management, with some additional events to incorporate origin and destination of the passengers. We prove NP-hardness of this problem, and we present an integer programming formulation for which we report the first numerical results. Furthermore, we discuss the variant in which we assume fixed costs for maintaining transfers and we present a polynomial algorithm for the special case of only one origin-destination pair.
Cite as

Twan Dollevoet, Dennis Huisman, Marie Schmidt, and Anita Schoebel. Delay Management with Re-Routing of Passengers. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dollevoet_et_al:OASIcs.ATMOS.2009.2143,
  author =	{Dollevoet, Twan and Huisman, Dennis and Schmidt, Marie and Schoebel, Anita},
  title =	{{Delay Management with Re-Routing of Passengers}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2143},
  URN =		{urn:nbn:de:0030-drops-21433},
  doi =		{10.4230/OASIcs.ATMOS.2009.2143},
  annote =	{Keywords: Transportation, Delay Management, Re-Routing, OD-pairs Transportation, Delay Management, Re-Routing, OD-pairs}
}
Document
DOI: 10.4230/DagSemProc.09261.30
The New Dutch Timetable: The OR Revolution

Authors: Dennis Huisman

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

Abstract
On April 14, 2008, INFORMS (The Institute for Operations Research and Management Sciences) announced Netherlands Railways to be the winner of the 2008 Franz Edelman Award. In this extended abstract, we give a short summary of both the paper and the presentation of the winning team.
Cite as

Dennis Huisman. The New Dutch Timetable: The OR Revolution. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{huisman:DagSemProc.09261.30,
  author =	{Huisman, Dennis},
  title =	{{The New Dutch Timetable: The OR Revolution}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.30},
  URN =		{urn:nbn:de:0030-drops-21696},
  doi =		{10.4230/DagSemProc.09261.30},
  annote =	{Keywords: Timetable}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2007.1168
07. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning

Authors: Erwin Abbink, Joel Van't Wout, and Dennis Huisman

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract
This paper deals with large-scale crew scheduling problems arising at the Dutch railway operator, Netherlands Railways (NS). We discuss several methods to partition large instances into several smaller ones. These smaller instances are then solved with the commercially available crew scheduling algorithm TURNI. In this paper, we compare several partitioning methods with each other. Moreover, we report some results where we applied different partitioning methods after each other. With this approach, we were able to cut crew costs with 2\% (about 6 million euro per year).
Cite as

Erwin Abbink, Joel Van't Wout, and Dennis Huisman. 07. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 96-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{abbink_et_al:OASIcs.ATMOS.2007.1168,
  author =	{Abbink, Erwin and Van't Wout, Joel and Huisman, Dennis},
  title =	{{07. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{96--106},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1168},
  URN =		{urn:nbn:de:0030-drops-11686},
  doi =		{10.4230/OASIcs.ATMOS.2007.1168},
  annote =	{Keywords: Crew scheduling, large-scale optimization, partitioning}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact